package com.sheng.leetcode.year2022.month10.day24;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/10/24
 *<p>
 * 915. 分割数组<p>
 *<p>
 * 给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：<p>
 * left 中的每个元素都小于或等于 right 中的每个元素。<p>
 * left 和 right 都是非空的。<p>
 * left 的长度要尽可能小。<p>
 * 在完成这样的分组后返回 left 的 长度 。<p>
 * 用例可以保证存在这样的划分方法。<p>
 *<p>
 * 示例 1：<p>
 * 输入：nums = [5,0,3,8,6]<p>
 * 输出：3<p>
 * 解释：left = [5,0,3]，right = [8,6]<p>
 *<p>
 * 示例 2：<p>
 * 输入：nums = [1,1,1,0,6,12]<p>
 * 输出：4<p>
 * 解释：left = [1,1,1,0]，right = [6,12]<p>
 *<p>
 * 提示：<p>
 * 2 <= nums.length <= 105<p>
 * 0 <= nums[i] <= 106<p>
 * 可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。<p>
 */
public class LeetCode0915 {

    @Test
    public void test01() {
//        int[] nums = {5,0,3,8,6};
        int[] nums = {1,1,1,0,6,12};
        System.out.println(new Solution().partitionDisjoint(nums));
    }
}
class Solution {
    public int partitionDisjoint(int[] nums) {
        int count = 0;
        int length = nums.length;
        // left 数组中最大的数的值
        int num = 0;
        // 是否满足 left 数组中的所有元素都小余等于 right 中的元素
        boolean flag = false;
        for (int i = 0; i < length; i++) {
            count++;
            // 判断大小
            num = Math.max(num, nums[i]);
            for (int j = i + 1; j < length; j++) {
                // 如果存在 right 数组中的值比最大值小，那么直接跳出本次循环
                if (nums[j] < num) {
                    flag = false;
                    break;
                } else if (j == length - 1) {
                    // 满足条件时
                    flag = true;
                }
            }
            if (flag) {
                return count;
            }
        }
        return count;
    }
}

//class Solution {
//    public int partitionDisjoint(int[] nums) {
//        int n = nums.length;
//        int[] min = new int[n + 10];
//        min[n - 1] = nums[n - 1];
//        for (int i = n - 2; i >= 0; i--) min[i] = Math.min(min[i + 1], nums[i]);
//        for (int i = 0, max = 0; i < n - 1; i++) {
//            max = Math.max(max, nums[i]);
//            if (max <= min[i + 1]) return i + 1;
//        }
//        return -1; // never
//    }
//}
//
//作者：宫水三叶
//链接：https://leetcode.cn/problems/partition-array-into-disjoint-intervals/solutions/1918958/by-ac_oier-yyen/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
